#include <iostream>
#include "LinkedList.h"

using namespace std;

// 100.00 %
class Solution
{
  public:
	ListNode *removeNthFromEnd(ListNode *head, int n)
	{
		ListNode *dummyHead = new ListNode(0);
		dummyHead->next = head;

		ListNode *p = dummyHead, *q = dummyHead;
		for (int i = 0; i < n; i++)
		{
			q = q->next;
		}
		while (q->next)
		{
			p = p->next;
			q = q->next;
		}
		ListNode *delNode = p->next;
		p->next = delNode->next;
		delete delNode;
		ListNode *retNode = dummyHead->next;
		return retNode;
	}
};

int main(int argc, char const *argv[])
{
	int arr[] = {1, 2, 3, 4, 5};
	int n = sizeof(arr) / sizeof(arr[0]);
	ListNode *list = createLinkedList(arr, n);
	int k = 2;
	printLinkedList(list);
	list = Solution().removeNthFromEnd(list, k);
	printLinkedList(list);
	deleteLinkedList(list);
	return 0;
}
